package com.wyw.leetcode.learning.simple;

/**
 * leetcode topic 235
 * 二叉搜索树的最近公共祖先
 *
 * @Author Mr Wu    yewen.wu.china@gmail.com
 * <p>
 * Update History:
 * Author        Time            Content
 */
public class Topic235 {

    static TreeNode result = null;
    public static void main(String[] args) {

    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if((root.val >= p.val && root.val <= q.val) || (root.val >= q.val && root.val <= p.val)) {
                return root;
            } else if(root.val < p.val && root.val < q.val) {
                root = root.right;
                lowestCommonAncestor(root, p, q);// 直接用会有错哦
            } else if(root.val > p.val && root.val > q.val) {
                root = root.left;
                lowestCommonAncestor(root, p, q);
            }
        }
        return null;
    }




    public static TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }

    public static TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        lca(root, p , q);
        return result;
    }

    public static void lca (TreeNode root, TreeNode p, TreeNode q) {
        if((root.val - p.val)*(root.val - q.val) <= 0){
            result = root;
        }else if(root.val < p.val && root.val < q.val){
            lca(root.right, p , q);
        }else{
            lca(root.left, p , q);
        }
    }

}

